最大数字

题目 最大数字

image-3d0249d5

思路分析

贪心吗

优先对高位进行操作 最高位达到9了再考虑第二位以此类推

貌似可行

第二个问题 对于4 能加4次 减5次 怎么选择 6 能加3次 减7次 怎么选择 有没有通用的公式 或者能不能直接枚举

而且还可以发现一个问题 对于某一位数 只会做一种操作 并不会搭配使用 因为是相消的

做第一种操作时（加） 要做9-x次才能到达9 如果到不了9 那就全给他让它尽可能大 即做A次 那么对于操作1 就是t=min(A,9-x)

做第二种操作（减） 只有变成0 再减1才会变成9 所以操作数应该是x+1次 如果到不了9 那干脆别做 只会越来越小 所以就是 能做就做x+1 不能做就不做

至于选了那种 就直接dfs 走不同的分支得到不同的结果 最后选择最大的

代码实现

#include<bits/stdc++.h>
using namespace std;
#define endl '\n'

typedef long long LL;
string s;
int A,B;
LL ans=0;

void dfs(int u,LL v){
	if(s[u]){
		int x=s[u]-'0';

		//第一种操作
		int op1=min(A,9-x);
		A-=op1;
		dfs(u+1,v*10+x+op1);
		A+=op1;

		//第二种操作
		if(B>x){
			B-=x+1;
			dfs(u+1,v*10+9);
			B+=x+1;
		}
	}
	else
		ans=max(ans,v);
}

int main()
{
	ios::sync_with_stdio(0),cin.tie(0),cout.tie(0);
	cin>>s>>A>>B;
	dfs(0,0);
	cout<<ans;
	return 0;
 }

同类题型

视频讲解

⬅️ 卡牌 🏠 00-冲刺国赛 ➡️ 出差